package com.mydemo.algorithm;

import java.util.*;

public class ThreeNum {

    public static void main(String[] args) {
        long s = System.currentTimeMillis();
        List<List<Integer>> lists = new ThreeNum().threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        System.out.println(System.currentTimeMillis() - s);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length < 3){
            return result;
        }
        int size = nums.length;
        int[] newArray = new int[size];
        Map<Integer, Integer> map = new HashMap<>();
        Set<String> cache = new HashSet<>();
        // 0的个数
        int zeroCount = 0;
        // 正指针
        int positive_point = size;
        // 负指针
        int negative_point = 0;

        // 复制到newArray,负数在左边, 正数在右边，
        for (int i = 0; i < size; i++) {
            int v = nums[i];
            if (v > 0) {
                newArray[--positive_point] = v;
                addSet(v, map);
            } else if (v < 0) {
                newArray[negative_point++] = v;
                addSet(v, map);
            } else {
                zeroCount++;
            }
        }

        if (zeroCount > 2) {
            addCache(0, 0, 0, cache, result);
        }

        if ((size - positive_point) == 0 || negative_point == 0){
            return result;
        }

        boolean zeroCountFlag = zeroCount > 0 ? true : false;
        for (int i = positive_point; i <= size - 1; i++) {
            for (int j = negative_point - 1; j >= 0; j--) {
                int start_v = newArray[j];
                int end_v = newArray[i];
                int three_v = -(start_v + end_v);
                if (three_v == 0) {
                    if (zeroCountFlag) {
                        addCache(start_v, 0, end_v, cache, result);
                    }
                } else if (three_v > 0) {
                    Integer count = map.get(three_v);
                    if (count != null && count > 0) {
                        if (three_v == end_v) {
                            if (count > 1) {
                                addCache(start_v, three_v, end_v, cache, result);
                            }
                        } else if (three_v > end_v) {
                            addCache(start_v, end_v, three_v, cache, result);
                        } else {
                            addCache(start_v, three_v, end_v, cache, result);
                        }
                    }
                } else {
                    Integer count = map.get(three_v);
                    if (count != null && count > 0) {
                        if (three_v == start_v) {
                            if (count > 1) {
                                addCache(start_v, three_v, end_v, cache, result);
                            }
                        } else if (three_v > start_v) {
                            addCache(start_v, three_v, end_v, cache, result);
                        } else {
                            addCache(three_v, start_v, end_v, cache, result);
                        }
                    }
                }
            }
        }
        return result;
    }


    void addCache(int x, int y, int z, Set<String> cache, List<List<Integer>> result) {
        String key = "" + x + y + z;
        if (!cache.contains(key)) {
            cache.add(key);
            result.add(Arrays.asList(x, y, z));
        }
    }

    void addSet(int value, Map<Integer, Integer> map) {
        Integer count = map.get(value);
        if (count == null) {
            count = 0;
        }
        map.put(value, ++count);
    }
}
